#include <bits/stdc++.h>
using namespace std;

/*
1061. 按字典序排列最小的等效字符串
已解答
中等
相关标签
premium lock icon
相关企业
提示
给出长度相同的两个字符串s1 和 s2 ，还有一个字符串 baseStr 。

其中  s1[i] 和 s2[i]  是一组等价字符。

举个例子，如果 s1 = "abc" 且 s2 = "cde"，那么就有 'a' == 'c', 'b' == 'd', 'c' == 'e'。
等价字符遵循任何等价关系的一般规则：

 自反性 ：'a' == 'a'
 对称性 ：'a' == 'b' 则必定有 'b' == 'a'
 传递性 ：'a' == 'b' 且 'b' == 'c' 就表明 'a' == 'c'
例如， s1 = "abc" 和 s2 = "cde" 的等价信息和之前的例子一样，那么 baseStr = "eed" , "acd" 或 "aab"，这三个字符串都是等价的，而 "aab" 是 baseStr 的按字典序最小的等价字符串

利用 s1 和 s2 的等价信息，找出并返回 baseStr 的按字典序排列最小的等价字符串。

 

示例 1：

输入：s1 = "parker", s2 = "morris", baseStr = "parser"
输出："makkek"
解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [m,p], [a,o], [k,r,s], [e,i] 共 4 组。每组中的字符都是等价的，并按字典序排列。所以答案是 "makkek"。
示例 2：

输入：s1 = "hello", s2 = "world", baseStr = "hold"
输出："hdld"
解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [h,w], [d,e,o], [l,r] 共 3 组。所以只有 S 中的第二个字符 'o' 变成 'd'，最后答案为 "hdld"。
示例 3：

输入：s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"
输出："aauaaaaada"
解释：我们可以把 A 和 B 中的等价字符分为 [a,o,e,r,s,c], [l,p], [g,t] 和 [d,m] 共 4 组，因此 S 中除了 'u' 和 'd' 之外的所有字母都转化成了 'a'，最后答案为 "aauaaaaada"。
 

提示：

1 <= s1.length, s2.length, baseStr <= 1000
s1.length == s2.length
字符串s1, s2, and baseStr 仅由从 'a' 到 'z' 的小写英文字母组成。
*/

// 法一
class Solution {
public:
    string smallestEquivalentString(string s1, string s2, string baseStr) {
        // 并查集
        vector<int> parent(26);
        // 初始化并查集，每个字符的父节点是自己
        for (int i = 0; i < 26; i++)    parent[i] = i;

        // 路径压缩 查找根节点
        auto find = [&](int x) -> int {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        };

        // 合并两个字符集合
        for (int i = 0; i < s1.size(); i++) {
            int a = s1[i] - 'a';
            int b = s2[i] - 'a';
            int rootA = find(a);
            int rootB = find(b);
            // 字典序小的作为根节点
            if (rootA != rootB) {
                if (rootA < rootB)  parent[rootB] = rootA;
                else    parent[rootA] = rootB;
            }
        }

        // 结果集
        string ans;
        for (char ch : baseStr) {
            int root = find(ch - 'a');
            ans += (char)(root + 'a');
        }
        return ans;
    }
};

// 法二
class Solution {
public:
    string smallestEquivalentString(string s1, string s2, string baseStr) {
        int equivalence_pairs_count = s1.size();  // 等价对的数量
        int base_str_length = baseStr.size();     // 目标字符串的长度
        
        // 使用数组代替unordered_map，因为字符范围固定(a-z)
        char parent[26];  // 父节点数组，索引0-25对应a-z
        
        // 初始化，每个字符的父节点指向自己
        for(int i = 0; i < 26; i++) {
            parent[i] = 'a' + i;
        }

        // 处理所有等价对
        for(int i = 0; i < equivalence_pairs_count; i++) {
            char char1 = s1[i];
            char char2 = s2[i];
            
            // 查找两个字符的根节点（带路径压缩）
            while (parent[char1 - 'a'] != char1) {
                // 路径压缩：将当前节点的父节点指向祖父节点
                parent[char1 - 'a'] = parent[parent[char1 - 'a'] - 'a'];
                char1 = parent[char1 - 'a'];
            }
            
            while (parent[char2 - 'a'] != char2) {
                parent[char2 - 'a'] = parent[parent[char2 - 'a'] - 'a'];
                char2 = parent[char2 - 'a'];
            }

            // 合并两个集合，总是让字典序较小的字符作为根
            if (char1 < char2) {
                parent[char2 - 'a'] = char1;
            } else if (char2 < char1) {
                parent[char1 - 'a'] = char2;
            }
            // 如果相等则无需处理
        }

        // 转换baseStr中的每个字符为其最小等价字符
        for (int i = 0; i < base_str_length; i++) {
            char current_char = baseStr[i];
            
            // 查找当前字符的最小等价字符
            while (parent[current_char - 'a'] != current_char) {
                // 路径压缩
                parent[current_char - 'a'] = parent[parent[current_char - 'a'] - 'a'];
                current_char = parent[current_char - 'a'];
            }
            baseStr[i] = current_char;
        }
        
        return baseStr;
    }
};

// 邻接表 图论DFS也行
// 法三
class Solution {
public:
    string smallestEquivalentString(string s1, string s2, string baseStr) {
        // 构建邻接表
        vector<vector<char>> adj(26);
        for (int i = 0; i < s1.size(); ++i) {
            char u = s1[i], v = s2[i];
            adj[u - 'a'].push_back(v);
            adj[v - 'a'].push_back(u);
        }

        // 记录每个字符的最小等价字符
        vector<char> minChar(26, ' ');
        
        // DFS 函数
        function<void(char, char)> dfs = [&](char node, char currentMin) {
            if (minChar[node - 'a'] != ' ') return; // 已访问
            minChar[node - 'a'] = currentMin;
            for (char neighbor : adj[node - 'a']) {
                dfs(neighbor, currentMin);
            }
        };

        // 为每个字符找到最小等价字符
        for (char c = 'a'; c <= 'z'; ++c) {
            if (minChar[c - 'a'] == ' ') {
                dfs(c, c); // 当前最小字符是自身
            }
        }

        // 转换 baseStr
        string result;
        for (char c : baseStr) {
            result += minChar[c - 'a'];
        }
        return result;
    }
};
